package 双指针技巧与相关题目;

// 供暖器
// 冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
// 在加热器的加热半径范围内的每个房屋都可以获得供暖。
// 现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置
// 请你找出并返回可以覆盖所有房屋的最小加热半径。
// 说明：所有供暖器都遵循你的半径标准，加热的半径也一样。
// 测试链接 : https://leetcode.cn/problems/heaters/

import java.util.Arrays;

public class Code06_Heaters {

    // 时间复杂度O(n * logn)，因为有排序，额外空间复杂度O(1)
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int ans = 0;
        for (int l = 0, r = 0; l < houses.length; l++) {
            // l 号房屋
            // r 号供暖器
            // 如果 l 号房屋 选择 r 号供暖器不是最优的，让供暖器移动
            while (!best(houses, heaters, l, r)) {
                r++;
            }
            // 是最优的，则计算当前房屋到供暖器的距离，并求最大值
            ans = Math.max(ans, Math.abs(houses[l] - heaters[r]));
        }
        return ans;
    }

    // 这个函数含义：
    // 当前的地点houses[l]由heaters[r]来供暖是最优的吗？
    // 当前的地点houses[l]由heaters[r]来供暖，产生的半径是a
    // 当前的地点houses[l]由heaters[r + 1]来供暖，产生的半径是b
    // 如果a < b, 说明是最优，供暖不应该跳下一个位置
    // 如果a >= b, 说明不是最优，应该跳下一个位置
    public static boolean best(int[] houses, int[] heaters, int l, int r) {
        // r == heaters.length - 1，供暖器的位置来到最后一个位置，那就是最优的
        // 之所以来到最后，就说明之前的供暖器不是最优了
        return r == heaters.length - 1
                ||
                Math.abs(houses[l] - heaters[r]) < Math.abs(houses[l] - heaters[r + 1]);
    }
}
